SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Bayesian-optimal pricing</title>

</head>

Bayesian-optimal pricing

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr">Bayesian-optimal pricing (BO pricing) is a kind of <a href="Algorithmic_pricing" title="Algorithmic pricing">algorithmic pricing</a> in which a seller determines the sell-prices based on probabilistic assumptions on the valuations of the buyers. It is a simple kind of a <a href="Bayesian-optimal_mechanism" title="Bayesian-optimal mechanism">Bayesian-optimal mechanism</a>, in which the price is determined in advance without collecting actual buyers' bids.

<div class="mw-heading mw-heading2"><h2 id="Single_item_and_single_buyer">Single item and single buyer</h2></div>

In the simplest setting, the seller has a single item to sell (with zero cost), and there is a single potential buyer. The highest price that the buyer is willing to pay for the item is called the valuation of the buyer. The seller would like to set the price exactly at the buyer's valuation. Unfortunately, the seller does not know the buyer's valuation. In the Bayesian model, it is assumed that the buyer's valuation is a <a href="Random_variable" title="Random variable">random variable</a> drawn from a known probability distribution.

Suppose the <a href="Cumulative_distribution_function" title="Cumulative distribution function">cumulative distribution function</a> of the buyer is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(v)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(v)}</annotation>

</semantics>

</math><img src="./4cf80e05072fd210ede15b7bb42cdc261abc2929.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.678ex; height:2.843ex;" alt="{\displaystyle F(v)}" loading="lazy">, defined as the probability that the seller's valuation is less than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy">. Then, if the price is set to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy">, the <a href="Expected_value" title="Expected value">expected value</a> of the seller's revenue is:<a href="#cite_note-r13-1">[1]</a>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Rev(p)=p\cdot (1-F(p))}</annotation>

</semantics>

</math><img src="./e11804162f4262555fb822c25eba01cf1993f71b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.432ex; height:2.843ex;" alt="{\displaystyle Rev(p)=p\cdot (1-F(p))}" loading="lazy"></dd></dl>

because the probability that the buyer will want to buy the item is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-F(p)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-F(p)}</annotation>

</semantics>

</math><img src="./9bb84a356f3283e83377d6d682157f2d6bd4cf8f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.722ex; height:2.843ex;" alt="{\displaystyle 1-F(p)}" loading="lazy">, and if this happens, the seller's revenue will be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy">.

The seller would like to find the price that maximizes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Rev(p)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Rev(p)}</annotation>

</semantics>

</math><img src="./6293493def70e9b73eb8e04502201cf8a3263ec1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.954ex; height:2.843ex;" alt="{\displaystyle Rev(p)}" loading="lazy">. The first-order condition, that the optimal price <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p^{*}}</annotation>

</semantics>

</math><img src="./180f741aa3ec0ac9e97e4777842b446c75bd4fa0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.676ex;" alt="{\displaystyle p^{*}}" loading="lazy"> should satisfy, is:

<msup>

</mrow>

</msup>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p^{*}={1-F(p^{*}) \over f(p^{*})}}</annotation>

</semantics>

</math><img src="./5bfd461081ca698ad2c46dc4a8417b6b344a35ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; margin-left: -0.089ex; width:16.024ex; height:6.509ex;" alt="{\displaystyle p^{*}={1-F(p^{*}) \over f(p^{*})}}" loading="lazy"></dd></dl>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(p)=F'(p)=}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(p)=F'(p)=}</annotation>

</semantics>

</math><img src="./9076ad68f060507cb5fa385c5dd7b5290942b750.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.287ex; height:3.009ex;" alt="{\displaystyle f(p)=F'(p)=}" loading="lazy"> the <a href="Probability_density_function" title="Probability density function">probability density function</a>.

For example, if the probability distribution of the buyer's valuation is uniform in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [a,a+d]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [a,a+d]}</annotation>

</semantics>

</math><img src="./630252147ed16d136e322c6a2eec0f07656e48c7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.844ex; height:2.843ex;" alt="{\displaystyle [a,a+d]}" loading="lazy">, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(v)=(v-a)/d}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(v)=(v-a)/d}</annotation>

</semantics>

</math><img src="./1ebabac98d30f5c622be00d5549ad5ce74d38aef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.162ex; height:2.843ex;" alt="{\displaystyle F(v)=(v-a)/d}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(v)=1/d}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(v)=1/d}</annotation>

</semantics>

</math><img src="./29876fa6be24abfb0b4e9488505fa72056fff515.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.855ex; height:2.843ex;" alt="{\displaystyle f(v)=1/d}" loading="lazy"> (in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [a,a+d]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [a,a+d]}</annotation>

</semantics>

</math><img src="./630252147ed16d136e322c6a2eec0f07656e48c7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.844ex; height:2.843ex;" alt="{\displaystyle [a,a+d]}" loading="lazy">). The first-order condition is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p^{*}=(a+d-p^{*})}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p^{*}=(a+d-p^{*})}</annotation>

</semantics>

</math><img src="./f870dfb337aa3597c75e53b6ee35acd266bddbb4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:17.571ex; height:2.843ex;" alt="{\displaystyle p^{*}=(a+d-p^{*})}" loading="lazy"> which implies <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p^{*}=(a+d)/2}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p^{*}=(a+d)/2}</annotation>

</semantics>

</math><img src="./5d267776cbb51fc4a7adb27691ec4220eaf415c9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:14.832ex; height:2.843ex;" alt="{\displaystyle p^{*}=(a+d)/2}" loading="lazy">. This is the optimal price only if it is in the range <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [a,a+d]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [a,a+d]}</annotation>

</semantics>

</math><img src="./630252147ed16d136e322c6a2eec0f07656e48c7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.844ex; height:2.843ex;" alt="{\displaystyle [a,a+d]}" loading="lazy"> (i.e., when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\leq d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\leq d}</annotation>

</semantics>

</math><img src="./d2bc300b41a26cab0e82b999f4cd2a8752e28f5a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.544ex; height:2.343ex;" alt="{\displaystyle a\leq d}" loading="lazy">).

Otherwise (when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\geq d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\geq d}</annotation>

</semantics>

</math><img src="./a9d37bdaafa41fa2586602bb37897935f7a89126.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.544ex; height:2.343ex;" alt="{\displaystyle a\geq d}" loading="lazy">), the optimal price is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p^{*}=a}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p^{*}=a}</annotation>

</semantics>

</math><img src="./ae62cd85abcbc9b2a64a64bee2d341b816bba9c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:6.641ex; height:2.676ex;" alt="{\displaystyle p^{*}=a}" loading="lazy">.

This optimal price has an alternative interpretation: it is the solution to the equation:

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w(p^{*})=0}</annotation>

</semantics>

</math><img src="./460bb215dcee3d959385a0f060381042f799e612.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.958ex; height:2.843ex;" alt="{\displaystyle w(p^{*})=0}" loading="lazy"></dd></dl>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy"> is the <a href="Virtual_valuation" title="Virtual valuation">virtual valuation</a> of the agent. So in this case, BO pricing is equivalent to the <a href="Bayesian-optimal_mechanism" title="Bayesian-optimal mechanism">Bayesian-optimal mechanism</a>, which is an auction with reserve-price <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p^{*}}</annotation>

</semantics>

</math><img src="./180f741aa3ec0ac9e97e4777842b446c75bd4fa0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.676ex;" alt="{\displaystyle p^{*}}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Single_item_and_many_buyers">Single item and many buyers</h2></div>

In this setting, the seller has a single item to sell (with zero cost), and there are multiple potential buyers whose valuations are a random vector drawn from some known probability distribution. Here, different pricing methods come to mind:<a href="#cite_note-bh08-2">[2]</a>

<ul><li>Symmetric prices: the seller sets a single price for the item. If one or more buyers accept this price, then one of them is selected arbitrarily.</li>

<li><a href="Discriminatory_prices" class="mw-redirect" title="Discriminatory prices">discriminatory prices</a>: the seller sets a different price for each buyer. If one or more buyers accept this price, then the buyer who accepted the highest price is selected. Discriminatory pricing can be implemented sequentially by ordering the prices in decreasing order and giving the item to the first buyer who accepts the price offered to him.</li></ul>

In the multiple-buyer setting, BO pricing is no longer equivalent to <a href="Bayesian-optimal_auction" class="mw-redirect" title="Bayesian-optimal auction">BO auction</a>: in pricing, the seller has to determine the price/s in advance, while in auction, the seller can determine the price based on the agents' bids. The competition between the buyers may enable the auctioneer to raise the price. Hence, in theory, the seller can obtain a higher revenue in an auction.

Example.<a href="#cite_note-chms10-3">[3]</a> There are two buyers whose valuations are distributed uniformly in the range <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [\$100,\$200]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [\$100,\$200]}</annotation>

</semantics>

</math><img src="./bee20f7aa9b11a412c5dac646733782f917c21c2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.627ex; height:2.843ex;" alt="{\displaystyle [\$100,\$200]}" loading="lazy">.

<ul><li>The BO auction is the <a href="Vickrey_auction" title="Vickrey auction">Vickrey auction</a> with reserve price $100 (= the inverse-virtual-valuation of 0). Its expected revenue is $133.</li>

<li>The BO discriminatory pricing scheme is to offer one agent a price of $150 and the other agent a price of $100. Its expected revenue is 0.5*150 + 0.5*100 = $125.</li></ul>

In practice, however, an auction is more complicated for the buyers since it requires them to declare their valuation in advance. The complexity of the auction process might deter buyers and ultimately lead to loss of revenue.<a href="#cite_note-am06-4">[4]</a><a href="#cite_note-h08-5">[5]</a> Therefore, it is interesting to compare the optimal pricing revenue to the optimal auction revenue, to see how much revenue the seller loses by using the simpler mechanism.

<div class="mw-heading mw-heading3"><h3 id="Buyers_with_independent_and_identical_valuations">Buyers with independent and identical valuations</h3></div>

Blumrosen and Holenstein<a href="#cite_note-bh08-2">[2]</a> study the special case in which the buyers' valuations are random variables drawn independently from the same probability distribution. They show that, when the distribution of the buyers' valuations has bounded support, BO-pricing and BO-auction converge to the same revenue. The convergence rate is asymptotically the same when <a href="Discriminatory_prices" class="mw-redirect" title="Discriminatory prices">discriminatory prices</a> are allowed, and slower by a logarithmic factor when symmetric prices must be used. For example, when the distribution is uniform in [0,1] and there are <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> potential buyers:

<ul><li>the revenue of the BO auction (a <a href="Vickrey_auction" title="Vickrey auction">Vickrey auction</a> with reserve price determined by the probability distribution) is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-2/n}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-2/n}</annotation>

</semantics>

</math><img src="./c9949c345a5899992140c851adb0e409eb10f282.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.722ex; height:2.843ex;" alt="{\displaystyle 1-2/n}" loading="lazy">;</li>

<li>the revenue of BO discriminatory pricing is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-4/n}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-4/n}</annotation>

</semantics>

</math><img src="./65d16acd58ba9e5d3ac96923a343534221f76efe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.722ex; height:2.843ex;" alt="{\displaystyle 1-4/n}" loading="lazy">;</li>

<li>the revenue of BO symmetric pricing is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-\log(n)/n}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-\log(n)/n}</annotation>

</semantics>

</math><img src="./578adce8b73a3896d5e3f4043ed392cb6824d792.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.736ex; height:2.843ex;" alt="{\displaystyle 1-\log(n)/n}" loading="lazy">.</li></ul>

In contrast, when the distribution of the buyers' valuations has unbounded support, the BO-pricing and the BO-auction might not converge to the same revenue. E.g., when the cdf is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(x)=1-1/x^{2}}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(x)=1-1/x^{2}}</annotation>

</semantics>

</math><img src="./26a89ab0786481203b12cf86e84360f0131cbb48.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.69ex; height:3.176ex;" alt="{\displaystyle F(x)=1-1/x^{2}}" loading="lazy">:

<ul><li>the revenue of the BO auction is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle .88{\sqrt {n}}}">

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle .88{\sqrt {n}}}</annotation>

</semantics>

</math><img src="./94826b62d8f2c26e07093252c7f6121ac880727a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.302ex; height:3.009ex;" alt="{\displaystyle .88{\sqrt {n}}}" loading="lazy">;</li>

<li>the revenue of BO discriminatory pricing is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle .7{\sqrt {n}}}">

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle .7{\sqrt {n}}}</annotation>

</semantics>

</math><img src="./110bafec469199845787353a4f770cf78cdeba8d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.14ex; height:3.009ex;" alt="{\displaystyle .7{\sqrt {n}}}" loading="lazy">;</li>

<li>the revenue of BO symmetric pricing is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle .64{\sqrt {n}}}">

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle .64{\sqrt {n}}}</annotation>

</semantics>

</math><img src="./e15adb000cdce477d515b03bcbe5a7531b1169d5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.302ex; height:3.009ex;" alt="{\displaystyle .64{\sqrt {n}}}" loading="lazy">.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Buyers_with_independent_and_different_valuations">Buyers with independent and different valuations</h3></div>

<a href="Shuchi_Chawla" title="Shuchi Chawla">Chawla</a> and Hartline and Malec and Sivan<a href="#cite_note-chms10-3">[3]</a> study the setting in which the buyers' valuations are random variables drawn independently from different probability distributions. Moreover, there are constraints on the set of agents that can be served together (for example: there is a limited number of units). They consider two kinds of discriminatory pricing schemes:

<ul><li>In an order-oblivious pricing mechanism (OPM), the mechanism-designer determines a price for each agent. The agents come in an arbitrary order. The mechanism guarantees are for worst-case (adversarial) order of the agents, determined after the agents' valuations are drawn.</li>

<li>In a sequential pricing mechanism (SPM), the mechanism-designer determines both a price for each agent, and an ordering on the agents. The mechanism loops over the agents in the pre-determined order. If the current agent can be served together with the previously-served agents (according to the constraints), then his personal price is offered to him, and he can either take it or leave it.</li></ul>

Their general scheme for calculating the prices is:

<ul><li>For each agent <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy">, calculate the probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q_{j}}</annotation>

</semantics>

</math><img src="./e0d567ac2d170501680d2efa4c1d71d6a8569ef1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:1.947ex; height:2.343ex;" alt="{\displaystyle q_{j}}" loading="lazy"> with which the BO mechanism (Myerson's mechanism) serves agent <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy">. This can be calculated either analytically or by simulations.</li>

<li>The price for agent <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"> is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{j}:=F_{j}^{-1}(1-C\cdot q_{j})}">

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{j}:=F_{j}^{-1}(1-C\cdot q_{j})}</annotation>

</semantics>

</math><img src="./e05089b6c0ad212ca1d0044943f26efc1ef544d8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; margin-left: -0.089ex; width:21.266ex; height:3.676ex;" alt="{\displaystyle p_{j}:=F_{j}^{-1}(1-C\cdot q_{j})}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> is a constant (either 1 or 1/2 or 1/3, depending on the setting). In other words, the price <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{j}}</annotation>

</semantics>

</math><img src="./499e0821b28c43e9bc2a6360b937de535057bc62.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; margin-left: -0.089ex; width:2.169ex; height:2.343ex;" alt="{\displaystyle p_{j}}" loading="lazy"> satisfies the following condition:</li></ul>

<dl><dd><dl><dd>Prob[the valuation of agent <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"> is at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{j}}</annotation>

</semantics>

</math><img src="./499e0821b28c43e9bc2a6360b937de535057bc62.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; margin-left: -0.089ex; width:2.169ex; height:2.343ex;" alt="{\displaystyle p_{j}}" loading="lazy">] = <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C\times }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C\times }</annotation>

</semantics>

</math><img src="./09122a685fc3a6e6d5c6468764c9b508dd4c8ecc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.574ex; height:2.176ex;" alt="{\displaystyle C\times }" loading="lazy"> Prob[the BO mechanism serves agent <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy">].</dd></dl></dd></dl>

If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C=1}</annotation>

</semantics>

</math><img src="./605a443c472808db9a502a801b8a2dfa5ee15d08.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.027ex; height:2.176ex;" alt="{\displaystyle C=1}" loading="lazy"> then the marginal-probability that an agent is served by the SPM is equal to the marginal-probability that it is served by the BO auction.

The approximation factors obtainable by an OPM depend on the structure of the constraints:<a href="#cite_note-chms10-3">[3]</a>: 318

<ul><li><a href="Uniform_matroid" title="Uniform matroid">uniform matroid</a> or <a href="Partition_matroid" title="Partition matroid">partition matroid</a> constraints - 2 (i.e, the revenue of the BO OPM is at least 1/2 the revenue of Myerson's BO auction).</li>

<li><a href="Graphic_matroid" title="Graphic matroid">graphic matroid</a> - 3</li>

<li>Intersection of two <a href="Partition_matroid" title="Partition matroid">partition matroids</a> - 6.75</li>

<li>Intersection of a graphic matroid and a partition matroid - 10.66</li>

<li>General matroid with <a href="Matroid_rank" title="Matroid rank">matroid rank</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> - <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log(k))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log(k))}</annotation>

</semantics>

</math><img src="./6524762f3f096433692188313c3ce866a7cbd3cc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.575ex; height:2.843ex;" alt="{\displaystyle O(\log(k))}" loading="lazy"></li></ul>

Moreover, they show two lower bounds:

<ul><li>An OPM cannot guarantee more than 1/2 the revenue of the BO auction, even in the single-item setting.</li>

<li>An OPM cannot guarantee more than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O({\log \log {n}/\log {n}})}">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O({\log \log {n}/\log {n}})}</annotation>

</semantics>

</math><img src="./3ddf9fa64c5fc10791d8dd152d8f2939b3f687dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.998ex; height:2.843ex;" alt="{\displaystyle O({\log \log {n}/\log {n}})}" loading="lazy"> the revenue of the BO auction when there are downwards-closed non-matroid constraint.</li></ul>

</div>

The approximation factors obtainable by an SPM are naturally better:

<ul><li>Uniform matroid, partition matroid - e/(e-1) ≅ 1.58</li>

<li>General matroid - 2</li>

<li>Intersection of two matroids - 3</li></ul>

The lower bound (proved by <a href="#cite_note-bh08-2">[2]</a>) is approximately 1.25.

Yan<a href="#cite_note-y10-6">[6]</a> explains the success of the sequential-pricing approach based on the concept of <a href="Correlation_gap" title="Correlation gap">correlation gap</a>, in the following way. The revenue of a mechanism is related to a set function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy">. E.g, in a k-unit auction, the function is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(S)=\min(|S|,k)}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(S)=\min(|S|,k)}</annotation>

</semantics>

</math><img src="./bf3ae563cb24f42fcb0917bd75702352d4a711ad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.408ex; height:2.843ex;" alt="{\displaystyle f(S)=\min(|S|,k)}" loading="lazy">

<ul><li>The revenue of the BO auction is at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(winners)\cdot Price}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(winners)\cdot Price}</annotation>

</semantics>

</math><img src="./bbfb6a91f5233ed0f08626cf4099ca0b91a5f988.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.932ex; height:2.843ex;" alt="{\displaystyle f(winners)\cdot Price}" loading="lazy">, where "Winners" is the set of k agents with highest valuations.</li>

<li>The revenue of the BO SPM is at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(Demand)\cdot Price}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(Demand)\cdot Price}</annotation>

</semantics>

</math><img src="./c46807d9876617410f428d356cec0563e3347556.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.342ex; height:2.843ex;" alt="{\displaystyle f(Demand)\cdot Price}" loading="lazy">, where "Demand" is the set of agents whose valuation is above the price.</li></ul>

Both "Winners" and "Demand" are random-sets, determined by the agents' valuations. Moreover, by carefully setting the price, it is possible to ensure that each agent <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"> has the same probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q_{j}}</annotation>

</semantics>

</math><img src="./e0d567ac2d170501680d2efa4c1d71d6a8569ef1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:1.947ex; height:2.343ex;" alt="{\displaystyle q_{j}}" loading="lazy"> to be in "Winners" and to be in "Demand". However, in "Winners", there is high correlation between different agents (if one agent wins, there is more probability that other agents lose), while in "Demand", the agents are independent. Therefore, the <a href="Correlation_gap" title="Correlation gap">correlation gap</a> is an upper bound on the loss of performance when using BO SPM instead of BO auction. This gives the following approximation factors:

<ul><li>General matroid - <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e/(e-1)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e/(e-1)}</annotation>

</semantics>

</math><img src="./f07826ef9b4d549e650947f62afe9d2809e04d67.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.142ex; height:2.843ex;" alt="{\displaystyle e/(e-1)}" loading="lazy"></li>

<li>k-unit auctions (a sub-case of general matroids) - <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1/(1-1/{\sqrt {2\pi k}})}">

</mrow>

</mrow>

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1/(1-1/{\sqrt {2\pi k}})}</annotation>

</semantics>

</math><img src="./e2457b2fd4d31b1c39631d620f705bfab9d8316b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.104ex; height:3.176ex;" alt="{\displaystyle 1/(1-1/{\sqrt {2\pi k}})}" loading="lazy"></li>

<li>p-independent set systems (a generalization of the intersection of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> matroids) - <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p+1}</annotation>

</semantics>

</math><img src="./5885ec01d3b5670fd5f88847f32da2b3dd62f60c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:5.262ex; height:2.509ex;" alt="{\displaystyle p+1}" loading="lazy">.</li></ul>

</div>

<div class="mw-heading mw-heading2"><h2 id="Different_items_and_one_unit-demand_buyer">Different items and one unit-demand buyer</h2></div>

In this setting, the seller has several different items for sale (e.g. cars of different models). There is one potential buyer, that is interested in a single item (e.g. a single car). The buyer has a different valuation for each item-type (i.e., he has a valuation-vector). Given the posted prices, the buyer buys the item that gives him the highest net utility (valuation minus price).

The buyer's valuation-vector is a random-vector from a multi-dimensional probability distribution. The seller wants to compute the price-vector (a price per item) that gives him the highest expected revenue.

Chawla and Hartline and Kleinberg<a href="#cite_note-chk07-7">[7]</a> study the case in which the buyer's valuations to the different items are independent random variables. They show that:

<ul><li>The revenue of the BO unit-demand pricing when there are <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> item-types is at most the revenue of the BO single-item auction when there are <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> potential buyers.</li>

<li>When the buyer's valuations to the different items are independent draws from the same distribution, the BO unit-demand pricing that uses the same price to all items attains at least 1/2.17 of the revenue of the BO single-item auction.<a href="#cite_note-8">[8]</a></li>

<li>When the buyer's valuations are independent draws from different distributions, the BO unit-demand pricing that uses the same virtual-price (based on <a href="Virtual_valuation" title="Virtual valuation">virtual valuations</a>) attains at least 1/3 of the revenue of the BO single-item auction.</li></ul>

They also consider the computational task of calculating the optimal price. The main challenge is to calculate <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w^{-1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w^{-1}}</annotation>

</semantics>

</math><img src="./403ebdcbddb58070ce67a3403489555e804173eb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.997ex; height:2.676ex;" alt="{\displaystyle w^{-1}}" loading="lazy">, the inverse of the virtual valuation function.

<ul><li>For discrete and regular valuation distribution, there is a polynomial-time 3-approximation.</li>

<li>For continuous and regular valuation distribution (available via an oracle) there is a polynomial-time (3+ε)-approximation <a href="With_high_probability" title="With high probability">with high probability</a>, and a faster (6+ε)-approximation with probability 1.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Different_items_and_many_unit-demand_buyers">Different items and many unit-demand buyers</h2></div>

In this setting, there are different types of items. Each buyer has different valuations for different items, and each buyer wants at most one item. Moreover, there are pre-specified constraints on the set of buyer-item pairs that can be allocated together (for example: each item can be allocated to at most one buyer; each buyer can get at most one item; etc).

Chawla and Hartline and Malec and Sivan<a href="#cite_note-chms10-3">[3]</a> study two kinds of discriminatory pricing schemes:

<ul><li>In a sequential pricing mechanism (SPM), the mechanism-designer determines a price for each buyer-item pair, and an ordering on the buyer-item pairs. The mechanism loops over the buyer-item pairs in the pre-determined order. If the current buyer-item pair is feasible, then the buyer is offered the item in the pre-determined price, and he can either take it or leave it.</li>

<li>In an order-oblivious pricing mechanism (OPM), the mechanism-designer determines a price for each buyer-item pair. The buyers come in an arbitrary order, which may be adversarially determined after the agents' valuations are drawn.</li></ul>

A sequential-pricing mechanism is, in general, not a <a href="Truthful_mechanism" class="mw-redirect" title="Truthful mechanism">truthful mechanism</a>, since an agent may decide to decline a good offer in hopes of getting a better offer later. It is truthful only when, for every buyer, the buyer-item pairs for that buyer are ordered in decreasing order of net-utility. Then, it is always best for the buyer to accept the first offer (if its net utility is positive). A special case of that situation is the single-parameter setting: for every buyer, there is only a single buyer-item pair (e.g, there is a single item for sale).

To every multi-parameter setting corresponds a single-parameter setting in which each buyer-item pair is considered an independent agent. In the single-parameter setting, there is more competition (since the agents that come from the same buyer compete with each other). Therefore, the BO revenue in the single-parameter setting is an upper bound on the BO revenue in the multi-parameter setting. Therefore, if an OPM is an r-approximation to the optimal mechanism for a single-parameter setting, then it is also an r-approximation to the corresponding multi-parameter setting.<a href="#cite_note-chms10-3">[3]</a> See <a href="#OPM">above</a> for approximation factors of OPMs in various settings.

See Chapter 7 "Multi-dimensional Approximation" in <a href="#cite_note-hartline12-9">[9]</a>: 124 for more details.

<div class="mw-heading mw-heading3"><h3 id="Many_unit-demand_buyers_and_sellers">Many unit-demand buyers and sellers</h3></div>

Recently, the SPM scheme has been extended to a <a href="Double_auction" title="Double auction">double auction</a> setting, where there are both buyers and sellers. The extended mechanism is called 2SPM. It is parametrized by an order on the buyers, an order on the sellers, and a matrix of prices - a price for each buyer-seller pair. The prices are offered to in order to buyers and sellers who may either accept or reject the offer. The approximation ratio is between 3 and 16, depending on the setting.<a href="#cite_note-10">[10]</a>

<ul><li><a href="Monopoly_pricing" class="mw-redirect" title="Monopoly pricing">Monopoly pricing</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFTim_Roughgarden2013" class="citation web cs1">Tim Roughgarden (2013). <a rel="nofollow" class="external text" href="http://theory.stanford.edu/~tim/f13/l/l5.pdf">"Revenue-Maximizing Auctions"</a> (PDF). Retrieved 19 July 2016.</cite>

</li>

<li id="cite_note-bh08-2">^ <a href="#cite_ref-bh08_2-0">a</a> <a href="#cite_ref-bh08_2-1">b</a> <a href="#cite_ref-bh08_2-2">c</a> <cite id="CITEREFBlumrosenHolenstein2008" class="citation conference cs1">Blumrosen, Liad; Holenstein, Thomas (2008). "Posted prices vs. Negotiations". Proceedings of the 9th ACM conference on Electronic commerce - EC '08. p. 49. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.221.9912">10.1.1.221.9912</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1386790.1386801">10.1145/1386790.1386801</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781605581699</bdi>.</cite>

</li>

<li id="cite_note-chms10-3">^ <a href="#cite_ref-chms10_3-0">a</a> <a href="#cite_ref-chms10_3-1">b</a> <a href="#cite_ref-chms10_3-2">c</a> <a href="#cite_ref-chms10_3-3">d</a> <a href="#cite_ref-chms10_3-4">e</a> <cite id="CITEREFChawlaHartlineMalecSivan2010" class="citation conference cs1"><a href="Shuchi_Chawla" title="Shuchi Chawla">Chawla, Shuchi</a>; Hartline, Jason D.; Malec, David L.; Sivan, Balasubramanian (2010). "Multi-parameter mechanism design and sequential posted pricing". Proceedings of the 42nd ACM symposium on Theory of computing - STOC '10. p. 311. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/0907.2435">0907.2435</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1806689.1806733">10.1145/1806689.1806733</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781450300506</bdi>.</cite>

</li>

<li id="cite_note-am06-4"><a href="#cite_ref-am06_4-0">^</a> <cite id="CITEREFAusubelMilgrom2005" class="citation book cs1">Ausubel, Lawrence M.; Milgrom, Paul (2005). "The Lovely but Lonely Vickrey Auction". Combinatorial Auctions. p. 17. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.7551%2Fmitpress%2F9780262033428.003.0002">10.7551/mitpress/9780262033428.003.0002</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780262033428</bdi>.</cite>

</li>

<li id="cite_note-h08-5"><a href="#cite_ref-h08_5-0">^</a> <cite id="CITEREFCatherine_Holahan2008" class="citation news cs1">Catherine Holahan (June 3, 2008). <a rel="nofollow" class="external text" href="https://www.bloomberg.com/news/articles/2008-06-03/auctions-on-ebay-a-dying-breedbusinessweek-business-news-stock-market-and-financial-advice">"Auctions on eBay: A Dying Breed"</a>. Bloomberg. Retrieved 1 July 2016.</cite>

</li>

<li id="cite_note-y10-6"><a href="#cite_ref-y10_6-0">^</a> <cite id="CITEREFYan2011" class="citation conference cs1">Yan, Qiqi (2011). "Mechanism Design via Correlation Gap". Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. p. 710. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1008.1843">1008.1843</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F1.9781611973082.56">10.1137/1.9781611973082.56</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-89871-993-2</bdi>.</cite>

</li>

<li id="cite_note-chk07-7"><a href="#cite_ref-chk07_7-0">^</a> <cite id="CITEREFChawlaHartlineKleinberg2007" class="citation conference cs1"><a href="Shuchi_Chawla" title="Shuchi Chawla">Chawla, Shuchi</a>; Hartline, Jason D.; Kleinberg, Robert (2007). "Algorithmic pricing via virtual valuations". Proceedings of the 8th ACM conference on Electronic commerce - EC '07. p. 243. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/0808.1671">0808.1671</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1250910.1250946">10.1145/1250910.1250946</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781595936530</bdi>.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> Single-price pricing is not necessarily the optimal pricing. For example, suppose there are two items, each with a value independently equal to 1 with probability 2/3 and 2 with probability 1/3. Then, the price-vectors (1,2) and (2,1) are optimal, but the price-vectors (1,1) and (2,2) are sub-optimal.

</li>

<li id="cite_note-hartline12-9"><a href="#cite_ref-hartline12_9-0">^</a> <cite id="CITEREFJason_D._Hartline2012" class="citation book cs1">Jason D. Hartline (2012). <a rel="nofollow" class="external text" href="https://jeremy-chen.org/sites/default/files/files/convexset/2012_11/amd.pdf">Approximation in Economic Design</a> (PDF).</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFColini-BaldeschiKeijzerLeonardiTurchetta2016" class="citation conference cs1">Colini-Baldeschi, Riccardo; Keijzer, Bart de; Leonardi, Stefano; Turchetta, Stefano (2016). "Approximately Efficient Double Auctions with Strong Budget Balance". Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. p. 1424. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F1.9781611974331.ch98">10.1137/1.9781611974331.ch98</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/11573%2F871600">11573/871600</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-61197-433-1</bdi>.</cite>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-12-09" href="https://en.wikipedia.org/wiki/?title=Bayesian-optimal_pricing&oldid=1262056941">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>